/**
 * @file mmedian.c
 * @note Copyright (C) 2013 Miroslav Lichvar <mlichvar@redhat.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
#include <stdlib.h>
#include <string.h>

#include "mmedian.h"
#include "filter_private.h"

// 定义mmedian结构体，用于存储移动中位数的相关信息。
struct mmedian {
    struct filter filter; // 过滤器接口。
    int cnt; // 当前存储的样本数量。
    int len; // 过滤器长度，即中位数计算的样本容量。
    int index; // 循环缓冲区的当前索引。
    int *order; // 存储样本索引的数组，按值排序。
    tmv_t *samples; // 存储样本值的循环缓冲区。
};


// 销毁mmedian过滤器的函数。
static void mmedian_destroy(struct filter *filter) {
    struct mmedian *m = container_of(filter, struct mmedian, filter);
    free(m->order); // 释放order数组。
    free(m->samples); // 释放samples数组。
    free(m); // 释放mmedian结构体本身。
}

// 计算并添加新样本的函数。
static tmv_t mmedian_sample(struct filter *filter, tmv_t sample) {
    struct mmedian *m = container_of(filter, struct mmedian, filter);
    int i;

    // 将新样本添加到循环缓冲区。
    m->samples[m->index] = sample;
    // 如果样本数量小于过滤器长度，增加样本计数。
    if (m->cnt < m->len) {
        m->cnt++;
    } else {
        // 如果样本数量等于过滤器长度，从order数组中移除被替换样本的索引。
        for (i = 0; i < m->cnt; i++)
            if (m->order[i] == m->index)
                break;
		// 样本向前平移
        for (; i + 1 < m->cnt; i++)
            m->order[i] = m->order[i + 1];
    }

    // 将新样本索引插入到order数组中的正确位置。
    for (i = m->cnt - 1; i > 0; i--) {
        if (m->samples[m->order[i - 1]] <= m->samples[m->index])
            break;
        m->order[i] = m->order[i - 1];
    }
    m->order[i] = m->index;

    // 更新循环缓冲区的索引。
    m->index = (1 + m->index) % m->len;

    // 根据样本数量的奇偶性，计算并返回中位数。
    if (m->cnt % 2)
		// 如果是奇数样本 
        return m->samples[m->order[m->cnt / 2]];
    else

		// 如果是偶数
        return tmv_div(
			tmv_add(
				m->samples[m->order[m->cnt / 2 - 1]],
				m->samples[m->order[m->cnt / 2]]
			), 
			2);
	}

// 重置mmedian过滤器的函数。
static void mmedian_reset(struct filter *filter) {
    struct mmedian *m = container_of(filter, struct mmedian, filter);
    m->cnt = 0; // 重置样本计数。
    m->index = 0; // 重置循环缓冲区索引。
}

// 创建mmedian过滤器的函数。
struct filter *mmedian_create(int length) {
    struct mmedian *m;

    if (length < 1)
        return NULL; // 如果长度小于1，返回NULL。

    m = calloc(1, sizeof(*m)); // 分配mmedian结构体内存。
    if (!m)
        return NULL;
    // 初始化过滤器接口的函数指针。
    m->filter.destroy = mmedian_destroy;
    m->filter.sample = mmedian_sample;
    m->filter.reset = mmedian_reset;

    m->order = calloc(1, length * sizeof(*m->order)); // 分配order数组内存。
    if (!m->order) {
        free(m); // 如果分配失败，释放mmedian结构体内存并返回NULL。
        return NULL;
    }
    m->samples = calloc(1, length * sizeof(*m->samples)); // 分配samples数组内存。
    if (!m->samples) {
        free(m->order); // 如果分配失败，释放order数组内存。
        free(m); // 释放mmedian结构体内存。
        return NULL;
    }

    m->len = length; // 设置过滤器长度。
    return &m->filter; // 返回过滤器接口指针。
}
